﻿#include "bin_image.h"
#include "../dependence/potrace/potracelib.h"
#include "../dependence/potrace/bitmap.h"
#include <algorithm>
#include <deque>

using namespace mdrawing;

namespace bin_image_implement
{
	struct UNIPoint
	{
		int X, Y;
		UNIPoint()
		{
			X = 0;
			Y = 0;
		}
		UNIPoint(int x, int y)
		{
			X = x;
			Y = y;
		}
	};
	template <class TYPE>
	class UNIStack
	{
		vector<TYPE> data;
	public:
		UNIStack(int n)
		{
			data.reserve(n);
			data.clear();
		}
		bool emp()
		{
			return (data.size() == 0);
		}
		void push(const TYPE &e)
		{
			data.push_back(e);
		}
		const TYPE &pop()
		{
			static TYPE e;
			e = data.back();
			data.pop_back();
			return e;
		}
		const TYPE &top()
		{
			return data.back();
		}
		void clear()
		{
			data.clear();
		}
		int len()
		{
			return data.size();
		}
	};
	template <class TYPE>
	class UNIQueue
	{
		vector<TYPE> data;
		int front, rear;
		const int MAX_SIZE;
	public:
		UNIQueue(int n) : MAX_SIZE(n)
		{
			data.resize(n);
			front = 0;
			rear = 0;
		}
		bool emp() const
		{
			return (front == rear);
		}
		void push(const TYPE &e)
		{
			data[rear] = e;
			rear = (rear + 1) % MAX_SIZE;
		}
		const TYPE &pop()
		{
			static TYPE e;
			if (emp()) return e;
			e = data[front];
			front = (front + 1) % MAX_SIZE;
			return e;
		}
		const TYPE &top() const
		{
			return data[(front + 1) % MAX_SIZE];
		}
		void clear()
		{
			front = 0;
			rear = 0;
		}
		int len()const
		{
			return (rear + MAX_SIZE - front) % MAX_SIZE;
		}
	};
	inline void point_to_bool(const vector<UNIPoint> &pt, int w, int h, vector<bool> &map)
	{
		int n = w * h;
		map.resize(n);
		for (int i = 0; i < n; i++)
			map[i] = false;
		for (int i = 0; i < int(pt.size()); i++)
			map[pt[i].Y*w + pt[i].X] = true;
	}
	inline void point_to_bool(const vector<vector<UNIPoint>> &pt, int w, int h, vector<bool> &map)
	{
		int n = w * h;
		map.resize(n);
		for (int i = 0; i < n; i++)
			map[i] = false;
		for (int i = 0; i < int(pt.size()); i++)
		for (int j = 0; j < int(pt[i].size()); j++)
			map[pt[i][j].Y*w + pt[i][j].X] = true;
	}
	
	//find_region
	inline void label_connect_region(int seed_x, int seed_y, vector<bool> &data, int w, int h, vector<UNIPoint> &region)
	{
		region.clear();
		int x = seed_x, y = seed_y;
		int pos = y * w + x;
		UNIStack<UNIPoint> stack(w*h + 1);
		//first seed
		{ data[pos] = false; region.push_back(UNIPoint(x, y)); stack.push(UNIPoint(x, y)); }
		//seed filling
		while (!stack.emp())
		{
			UNIPoint pt = stack.pop();
			//left
			x = pt.X - 1; y = pt.Y; pos = y * w + x;
			if (x >= 0 && data[pos]) { data[pos] = false; region.push_back(UNIPoint(x, y)); stack.push(UNIPoint(x, y)); }
			//right
			x = pt.X + 1; y = pt.Y; pos = y * w + x;
			if (x < w  && data[pos]) { data[pos] = false; region.push_back(UNIPoint(x, y)); stack.push(UNIPoint(x, y)); }
			//up
			x = pt.X; y = pt.Y - 1; pos = y * w + x;
			if (y >= 0 && data[pos]) { data[pos] = false; region.push_back(UNIPoint(x, y)); stack.push(UNIPoint(x, y)); }
			//down
			x = pt.X; y = pt.Y + 1; pos = y * w + x;
			if (y < h  && data[pos]) { data[pos] = false; region.push_back(UNIPoint(x, y)); stack.push(UNIPoint(x, y)); }
		}
	}
	inline void find_all_regions(const vector<bool> &data, int w, int h, int MN, int MX, vector<vector<UNIPoint>> &dst)
	{
		vector<bool> a = data;
		dst.clear();
		vector<UNIPoint> region;
		for (int j = 0; j < h; j++)
			for (int i = 0; i < w; i++)
			{
				if (a[j*w + i])
				{
					region.clear();
					label_connect_region(i, j, a, w, h, region);
					int pt_num = int(region.size());
					if (pt_num >= MN && pt_num <= MX)
						dst.push_back(region);
				}
			}
	}
	inline void find_all_regions(const vector<bool> &data, int w, int h, int QUALI_SIZE, vector<vector<UNIPoint>> &dst)
	{
		find_all_regions(data, w, h, QUALI_SIZE, INT_MAX, dst);
	}
	inline void find_all_regions(const vector<bool> &data, int w, int h, vector<vector<UNIPoint>> &dst)
	{
		vector<bool> a = data;
		dst.clear();
		vector<UNIPoint> region;
		for (int j = 0; j < h; j++)
			for (int i = 0; i < w; i++)
			{
				if (a[j*w + i])
				{
					region.clear();
					label_connect_region(i, j, a, w, h, region);
					dst.push_back(region);
				}
			}
	}
	inline bool find_largest_regions(const vector<bool> &data, int w, int h, int QUALI_SIZE, vector<UNIPoint> &dst)
	{
		vector<bool> a = data;
		dst.clear();
		vector<UNIPoint> region;
		int max_num = 0;
		for (int j = 0; j < h; j++)
		for (int i = 0; i < w; i++)
		{
			if (a[j*w + i])
			{
				region.clear();
				label_connect_region(i, j, a, w, h, region);
				int pixel_num = int(region.size());
				if (pixel_num>QUALI_SIZE && pixel_num > max_num)
				{
					max_num = pixel_num;
					dst = region;
				}
			}
		}
		return (max_num > 0);
	}
	
	//bool_map
	inline void label_island(const vector<bool> &data, int w, int h, vector<bool> &island)
	{
		//根据阈值计算mask
		vector<bool> mask = data;
		int n = w * h;
		island.resize(n);
		for (int i = 0; i < n; i++)
			island[i] = true;

		//Add Seeds
		UNIStack<UNIPoint> stack(n + 1);
		for (int x = 0; x < w; x++)
		{
			island[x] = false;
			mask[x] = true;
			stack.push(UNIPoint(x, 0));

			island[(w*(h - 2)) + x] = false;
			mask[(w*(h - 2)) + x] = true;
			stack.push(UNIPoint(x, h - 1));
		}
		for (int y = 0; y < h; y++)
		{
			island[w*y] = false;
			mask[w*y] = true;
			stack.push(UNIPoint(0, y));

			island[(w*y) + (w - 1)] = false;
			mask[(w*y) + (w - 1)] = true;
			stack.push(UNIPoint(w - 1, y));
		}
		//seed filling
		int x, y, pos;
		while (!stack.emp())
		{
			UNIPoint pt = stack.pop();
			//left
			x = pt.X - 1; y = pt.Y; pos = y * w + x;
			if (x >= 0 && mask[pos]) { island[pos] = false; mask[pos] = false; stack.push(UNIPoint(x, y)); }
			//right
			x = pt.X + 1; y = pt.Y; pos = y * w + x;
			if (x < w && mask[pos]) { island[pos] = false; mask[pos] = false; stack.push(UNIPoint(x, y)); }
			//up
			x = pt.X; y = pt.Y - 1; pos = y * w + x;
			if (y >= 0 && mask[pos]) { island[pos] = false; mask[pos] = false; stack.push(UNIPoint(x, y)); }
			//down
			x = pt.X; y = pt.Y + 1; pos = y * w + x;
			if (y < h && mask[pos]) { island[pos] = false; mask[pos] = false; stack.push(UNIPoint(x, y)); }
		}
	}
	inline void bool_operate_NOT(vector<bool> &bin)
	{
		int n = int(bin.size());
		for (int i = 0; i < n; i++)
			bin[i] = !bin[i];
	}
	inline void bool_operate_AND(const vector<bool> &s1, const vector<bool> &s2, vector<bool> &dst)
	{
		int n = int(s1.size());
		dst.resize(n);
		for (int i = 0; i < n; i++)
			dst[i] = (s1[i] && s2[i]);
	}
	inline void bool_operate_SUB(const vector<bool> &s1, const vector<bool> &s2, vector<bool> &dst)
	{
		int n = int(s1.size());
		dst.resize(n);
		for (int i = 0; i < n; i++)
			dst[i] = (s1[i] && !s2[i]);
	}
	inline void bool_operate_OR(const vector<bool> &s1, const vector<bool> &s2, vector<bool> &dst)
	{
		int n = int(s1.size());
		dst.resize(n);
		for (int i = 0; i < n; i++)
			dst[i] = (s1[i] || s2[i]);
	}
	inline void bool_operate_XOR(const vector<bool> &s1, const vector<bool> &s2, vector<bool> &dst)
	{
		int n = int(s1.size());
		dst.resize(n);
		for (int i = 0; i < n; i++)
			dst[i] = (s1[i]!=s2[i]);
	}
	inline void generate_edge(const vector<bool> &canvas, int w, int h, const int &R, vector<bool> &canvas_edge)
	{
		deque<UNIPoint> stack;
		deque<int> level;
		int n = w * h;
		canvas_edge.resize(n);
		for (int i = 0; i < n; i++)
			canvas_edge[i] = false;

		//Add Seeds
		vector<bool> t = canvas;
		int count = 0;
		for (int y = 1; y < h - 1; y++)
			for (int x = 1; x < w - 1; x++)
			{
				int pos = y * w + x;
				if (canvas[pos] && (!canvas[pos - 1] || !canvas[pos + 1] || !canvas[pos + w] || !canvas[pos - w]))//不能用t，t会被动态修改
				{
					stack.push_back(UNIPoint(x, y));
					level.push_back(1);
					t[pos] = false;
					canvas_edge[pos] = true;
				}
			}

		int x, y, pos;
		while (stack.size() > 0)
		{
			auto &pt = stack.front();
			int   d = level.front() + 1;
			if (d > R) break;

			//left
			x = pt.X - 1; y = pt.Y; pos = y * w + x;
			if (x >= 0 && t[pos]) { stack.push_back(UNIPoint(x, y)); level.push_back(d); t[pos] = false; canvas_edge[pos] = true; }
			//right
			x = pt.X + 1; y = pt.Y; pos = y * w + x;
			if (x < w && t[pos]) { stack.push_back(UNIPoint(x, y)); level.push_back(d); t[pos] = false; canvas_edge[pos] = true; }
			//up
			x = pt.X; y = pt.Y - 1; pos = y * w + x;
			if (y >= 0 && t[pos]) { stack.push_back(UNIPoint(x, y)); level.push_back(d); t[pos] = false; canvas_edge[pos] = true; }
			//down
			x = pt.X; y = pt.Y + 1; pos = y * w + x;
			if (y < h &&  t[pos]) { stack.push_back(UNIPoint(x, y)); level.push_back(d); t[pos] = false; canvas_edge[pos] = true; }

			stack.pop_front();
			level.pop_front();
		}
	}
	inline void add_shadow_edge(const vector<bool> &canvas, int w, int h, const int &DX, const int &DY, vector<bool> &canvas_edge)
	{
		for (int j = 0; j < DY; j++)
			for (int i = 0; i < DX; i++)
			{
				int off = j * w + i;
				canvas_edge[off] = true;
			}
	}
	inline void dilate(vector<bool> &data, int w, int h, const int &R)
	{
		//Add Seeds
		UNIQueue<UNIPoint> queue(w*h + 10);
		UNIQueue<int>      level(w*h + 10);
		for (int y = 0; y < h; y++)
			for (int x = 0; x < w; x++)
			{
				if (data[y * w + x])
				{
					queue.push(UNIPoint(x, y));
					level.push(0);
				}
			}
		int x, y, pos;
		while (!queue.emp())
		{
			auto &pt = queue.pop();
			int   d = level.pop() + 1;
			if (d > R) break;
			//left
			x = pt.X - 1; y = pt.Y; pos = y * w + x;
			if (x >= 0 && !data[pos]) { queue.push(UNIPoint(x, y)); level.push(d); data[pos] = true; }
			//right
			x = pt.X + 1; y = pt.Y; pos = y * w + x;
			if (x < w && !data[pos]) { queue.push(UNIPoint(x, y)); level.push(d); data[pos] = true; }
			//up
			x = pt.X; y = pt.Y - 1; pos = y * w + x;
			if (y >= 0 && !data[pos]) { queue.push(UNIPoint(x, y)); level.push(d); data[pos] = true; }
			//down
			x = pt.X; y = pt.Y + 1; pos = y * w + x;
			if (y < h && !data[pos]) { queue.push(UNIPoint(x, y)); level.push(d); data[pos] = true; }

			//left_up
			x = pt.X - 1; y = pt.Y - 1; pos = y * w + x;
			if (x >= 0 && y >= 0 && !data[pos]) { queue.push(UNIPoint(x, y)); level.push(d); data[pos] = true; }
			//right_up
			x = pt.X + 1; y = pt.Y - 1; pos = y * w + x;
			if (x < w && y >= 0 && !data[pos]) { queue.push(UNIPoint(x, y)); level.push(d); data[pos] = true; }
			//left_down
			x = pt.X - 1; y = pt.Y + 1; pos = y * w + x;
			if (x >= 0 && y < h && !data[pos]) { queue.push(UNIPoint(x, y)); level.push(d); data[pos] = true; }
			//right_down
			x = pt.X + 1; y = pt.Y + 1; pos = y * w + x;
			if (x < w && y < h && !data[pos]) { queue.push(UNIPoint(x, y)); level.push(d); data[pos] = true; }
		}
	}
	inline void erose(vector<bool> &data, int w, int h, const int &R)
	{
		//Add Seeds
		UNIQueue<UNIPoint> stack(w*h + 10);
		UNIQueue<int>      level(w*h + 10);
		for (int y = 0; y < h; y++)
			for (int x = 0; x < w; x++)
			{
				if (false == data[y * w + x])
				{
					stack.push(UNIPoint(x, y));
					level.push(0);
				}
			}
		int x, y, pos;
		while (!stack.emp())
		{
			auto &pt = stack.pop();
			int   d = level.pop() + 1;
			if (d > R) break;
			//left
			x = pt.X - 1; y = pt.Y; pos = y * w + x;
			if (x >= 0 && data[pos]) { stack.push(UNIPoint(x, y)); level.push(d); data[pos] = false; }
			//right
			x = pt.X + 1; y = pt.Y; pos = y * w + x;
			if (x < w && data[pos]) { stack.push(UNIPoint(x, y)); level.push(d); data[pos] = false; }
			//up
			x = pt.X; y = pt.Y - 1; pos = y * w + x;
			if (y >= 0 && data[pos]) { stack.push(UNIPoint(x, y)); level.push(d); data[pos] = false; }
			//down
			x = pt.X; y = pt.Y + 1; pos = y * w + x;
			if (y < h && data[pos]) { stack.push(UNIPoint(x, y)); level.push(d); data[pos] = false; }

			//left_up
			x = pt.X - 1; y = pt.Y - 1; pos = y * w + x;
			if (x >= 0 && y >= 0 && data[pos]) { stack.push(UNIPoint(x, y)); level.push(d); data[pos] = false; }
			//right_up
			x = pt.X + 1; y = pt.Y - 1; pos = y * w + x;
			if (x < w && y >= 0 && data[pos]) { stack.push(UNIPoint(x, y)); level.push(d); data[pos] = false; }
			//left_down
			x = pt.X - 1; y = pt.Y + 1; pos = y * w + x;
			if (x >= 0 && y < h && data[pos]) { stack.push(UNIPoint(x, y)); level.push(d); data[pos] = false; }
			//right_down
			x = pt.X + 1; y = pt.Y + 1; pos = y * w + x;
			if (x < w && y < h && data[pos]) { stack.push(UNIPoint(x, y)); level.push(d); data[pos] = false; }
		}
	}
	inline void dilate(vector<bool> &data, int w, int h)
	{
		vector<bool> t = data;
		for (int i = 1; i < w - 1; i++)
			for (int j = 1; j < h - 1; j++)
			{
				int pos = j * w + i;
				if (t[pos])
				{
					pos -= (w + 1); data[pos] = true;
					pos++;      data[pos] = true;
					pos++;      data[pos] = true;
					pos += w;   data[pos] = true;
					pos -= 2;   data[pos] = true;
					pos += w;   data[pos] = true;
					pos++;      data[pos] = true;
					pos++;      data[pos] = true;
				}
			}
	}
	inline void erose(vector<bool> &data, int w, int h)
	{
		vector<bool> t = data;
		for (int i = 1; i < w - 1; i++)
			for (int j = 1; j < h - 1; j++)
			{
				int pos = j * w + i;
				if (!t[pos])
				{
					pos -= (w + 1); data[pos] = false;
					pos++;      data[pos] = false;
					pos++;      data[pos] = false;
					pos += w;   data[pos] = false;
					pos -= 2;   data[pos] = false;
					pos += w;   data[pos] = false;
					pos++;      data[pos] = false;
					pos++;      data[pos] = false;
				}
			}
	}
	inline void fill_region(vector<bool> &data, int w, int h)
	{
		vector<bool> b = data;
		for (int i = 0; i < w*h; i++)
			data[i] = true;
		UNIStack<UNIPoint> stack(w*h + 1);
		//
		//Add Seeds
		//
		for (int x = 0; x < w; x++)
		{
			b[x] = false; data[x] = false; stack.push(UNIPoint(x, 0));
			b[(w*(h - 2)) + x] = false;  data[(w*(h - 2)) + x] = false; stack.push(UNIPoint(x, h - 1));
		}
		for (int y = 0; y < h; y++)
		{
			b[w*y] = false;  data[w*y] = false; stack.push(UNIPoint(0, y));
			b[(w*y) + (w - 1)] = false; data[(w*y) + (w - 1)] = false; stack.push(UNIPoint(w - 1, y));
		}
		//
		//seed filling
		//
		int x, y, pos;
		while (!stack.emp())
		{
			UNIPoint pt = stack.pop();
			//left
			x = pt.X - 1; y = pt.Y; pos = y * w + x;
			if (x >= 0 && !b[pos] && data[pos]) { data[pos] = false; stack.push(UNIPoint(x, y)); }
			//right
			x = pt.X + 1; y = pt.Y; pos = y * w + x;
			if (x < w && !b[pos] && data[pos]) { data[pos] = false; stack.push(UNIPoint(x, y)); }
			//up
			x = pt.X; y = pt.Y - 1; pos = y * w + x;
			if (y >= 0 && !b[pos] && data[pos]) { data[pos] = false; stack.push(UNIPoint(x, y)); }
			//down
			x = pt.X; y = pt.Y + 1; pos = y * w + x;
			if (y < h && !b[pos] && data[pos]) { data[pos] = false; stack.push(UNIPoint(x, y)); }
		}
	}

	//颜色处理
	inline bool is_white_paper(const vector<bool> &canvas, const vector<bool> &candidate_pen, const vector<Color> &color, int w, int h)
	{
		int count = 0, sum_R = 0, sum_G = 0, sum_B = 0;
		int n = w * h;
		for (int i = 0; i < n; i++)
		{
			if (canvas[i] && !candidate_pen[i])
			{
				auto &t = color[i];
				sum_R += t.R;
				sum_G += t.G;
				sum_B += t.B;
				count++;
			}
		}
		const int BOARD_NUM_THRESHOLD = 100000;
		const int MIN_RGB_THRESHOLD = 30;
		const float RGB_PERCENT_THRESHOLD = 1.25f;
		//printf("board num: %d\n", count);
		if (count > BOARD_NUM_THRESHOLD)
		{
			int MAX = max(max(sum_R, sum_G), sum_B);
			int MIN = min(min(sum_R, sum_G), sum_B);
			printf("white paper: %.2f\n", float(MAX) / float(MIN));
			if (MIN > MIN_RGB_THRESHOLD && float(MAX) / float(MIN) < RGB_PERCENT_THRESHOLD)
			{
				return true;
			}
		}
		return false;
	}
	inline bool is_red_pen(const Color &c)
	{
		if (c.R < 40 && c.G < 40 && c.B < 40) return false;
		if (c.R > 200 && c.G > 200 && c.B > 200) return false;
		//float per_R = 1.5f*((c.R + c.R) - (c.G + c.B)) / (c.R + c.G + c.B);
		//float per_B = 1.5f*((B + B) - (R + G)) / (R + G + B);
		//float per_G = 1.5f*((G + G) - (R + B)) / (R + G + B);

		//if (per_R > 0.2f) return true;
		//if (per_B > 0.1f) return BLUE;
		//if (per_G > 0.15f) return GREEN;*/

		if (c.R - c.G > 20 && c.R - c.B > 20) return true;
		//if (G - R > 20 && G - B > 20) return GREEN;
		//if (B - R > 10 && B - G > 10) return BLUE;
		//if (G - R > 20 || B - R > 20) return BLUE;
		if (c.R > 40 && float(c.G) / float(c.R) < 0.9f && float(c.G) / float(c.R) < 0.9f) return true;
		//if (G > 50 && 1.0f*R / G < 0.9f && 1.0f*B / G < 0.9f) return GREEN;
		//if (B > 50 && 1.0f*R / B < 0.9f && 1.0f*G / B < 0.9f) return BLUE;//*/
		return false;
	}
	inline void detect_red(const vector<bool> &pen, const vector<Color> &color, int w, int h, vector<bool> &black, vector<bool> &red)
	{
		int n = w * h;
		black.resize(n);
		red.resize(n);
		for (int i = 0; i < n; i++)
		{
			if (is_red_pen(color[i]))
			{
				red[i] = pen[i];
				black[i] = false;
			}
			else
			{
				red[i] = false;
				black[i] = pen[i];
			}
		}
	}
	inline Color get_average_color(const vector<UNIPoint> &pt, const vector<Color> &color, int w, int h)
	{
		int n = int(pt.size());
		if (n == 0) return Color(0, 0, 0);
		int sum_R = 0, sum_G = 0, sum_B = 0;
		for (int i = 0; i<n; i++)
		{
			int off = pt[i].Y*w + pt[i].X;
			sum_R += color[off].R;
			sum_G += color[off].G;
			sum_B += color[off].B;
		}
		return Color(sum_R / n, sum_G / n, sum_B / n);
	}
	inline void detect_red(const vector<vector<UNIPoint>> &region, const vector<Color> &color, int w, int h,
		vector<vector<UNIPoint>> &red, vector<vector<UNIPoint>> &black)
	{
		red.clear();
		black.clear();
		for (int i = 0; i<int(region.size()); i++)
		{
			Color c = get_average_color(region[i], color, w, h);
			if (is_red_pen(c))
				red.push_back(region[i]);
			else
				black.push_back(region[i]);
		}
	}
	inline void identify_red_black(const vector<bool> &pen, const vector<Color> &color, int w, int h, vector<bool> &black, vector<bool> &red)
	{
		const int EP = 50; //50 = 2mm X 2mm
		vector<vector<UNIPoint>> pen_region;
		find_all_regions(pen, w, h, EP, pen_region);

		vector<vector<UNIPoint>> red_region, black_region;
		detect_red(pen_region, color, w, h, red_region, black_region);

		point_to_bool(black_region, w, h, black);
		point_to_bool(red_region, w, h, red);
	}

	//potrace
	inline potrace_bitmap_t *bm_new(vector<bool> &data, int w, int h)
	{
		int dy = (w + BM_WORDBITS - 1) / BM_WORDBITS;
		potrace_bitmap_t *bm = (potrace_bitmap_t *)malloc(sizeof(potrace_bitmap_t));
		if (!bm) return NULL;
		bm->w = w;
		bm->h = h;
		bm->dy = dy;
		bm->map = (potrace_word *)calloc(h, dy * BM_WORDSIZE);
		if (!bm->map) {
			free(bm);
			return NULL;
		}
		for (int y = 0; y < h; y++)
			for (int x = 0; x < w; x++)
				BM_PUT(bm, x, y, data[y*w + x] ? 1 : 0);
		return bm;
	}
	inline void rgb_to_bin(const unsigned char rgb[], int w, int h, vector<bool> &bin)
	{
		const int BIN_THRESHOLD = 127;
		bin.resize(w*h);
		for (int i = 0; i < int(w*h); i++)
			bin[i] = (rgb[i * 3] < BIN_THRESHOLD);
	}
	inline void add_bezier_points(const Point &pt0, const Point &pt1, const Point &pt2, const Point &pt3, vector<Point> &dst)
	{
		const int DIV_NUM = 8;
		static const double B0[DIV_NUM] = {
			1.000000000000, 0.629737609329, 0.364431486880, 0.186588921283,
			0.078717201166, 0.023323615160, 0.002915451895, 0.000000000000 };
		static const double B1[DIV_NUM] = {
			0.000000000000, 0.314868804665, 0.437317784257, 0.419825072886,
			0.314868804665, 0.174927113703, 0.052478134111, 0.000000000000 };
		static const double B2[DIV_NUM] = {
			0.000000000000, 0.052478134111, 0.174927113703, 0.314868804665,
			0.419825072886, 0.437317784257, 0.314868804665, 0.000000000000 };
		static const double B3[DIV_NUM] = {
			0.000000000000, 0.002915451895, 0.023323615160, 0.078717201166,
			0.186588921283, 0.364431486880, 0.629737609329, 1.000000000000 };
		//////////////////////////////////////////////////////////////////////////////////////
		Point pt;
		for (int j = 0; j < DIV_NUM; j++) //- 1/*最后一点与下条线段的第一点冗余*/
		{
			pt.X = float(pt0.X*B0[j] + pt1.X*B1[j] + pt2.X*B2[j] + pt3.X*B3[j]);
			pt.Y = float(pt0.Y*B0[j] + pt1.Y*B1[j] + pt2.Y*B2[j] + pt3.Y*B3[j]);
			dst.push_back(pt);
		}
	}
	inline void potrace(vector<bool> &bin_image, int w, int h, vector<vector<Point>> &path)
	{
		//
		//bitmap
		//
		potrace_bitmap_t *bm = bm_new(bin_image, w, h);
		//
		//parameters
		//
		potrace_param_t *param = potrace_param_default();
		param->turdsize = 0;
		//
		//potrace
		//
		potrace_state_t *st = potrace_trace(param, bm);
		if (!st || st->status != POTRACE_STATUS_OK) {
			fprintf(stderr, "Error tracing bitmap: %s\n", strerror(errno));
			return;
		}
		bm_free(bm);
		//
		//draw each curve
		//
		path.clear();
		Point pt;
		vector<Point> t;
		potrace_path_t *p = st->plist;
		while (p)
		{
			int n = p->curve.n;
			int *tag = p->curve.tag;
			auto  *c = p->curve.c;
			t.clear();
			t.push_back(Point(float(c[n - 1][2].x), float(c[n - 1][2].y)));
			for (int i = 0; i < n; i++)
			{
				switch (tag[i])
				{
				case POTRACE_CORNER:
					t.push_back(Point(float(c[i][1].x), float(c[i][1].y)));
					t.push_back(Point(float(c[i][2].x), float(c[i][2].y)));
					break;
				case POTRACE_CURVETO:
					pt = t.back();
					add_bezier_points(pt,
						Point(float(c[i][0].x), float(c[i][0].y)),
						Point(float(c[i][1].x), float(c[i][1].y)),
						Point(float(c[i][2].x), float(c[i][2].y)), t);
					break;
				}
			}
			if (t.size() > 1)
				path.push_back(t);
			p = p->next;
		}
		//
		//free
		//
		potrace_state_free(st);
		potrace_param_free(param);
	}

	//生成路径
	inline void generate_cut_path(const vector<bool> &map, int w, int h, vector<vector<Point>> &paths)
	{
		auto t = map;
		dilate(t, w, h);
		fill_region(t, w, h);
		erose(t, w, h);
		potrace(t, w, h, paths);
	}
	inline void generate_cut_path_all_level(const vector<bool> &map, int w, int h, vector<vector<Point>> &paths)
	{
		vector<bool> bin = map;

		const int PEN_SIZE = 50; //约2mm X 2mm
		vector<vector<UNIPoint>> child;
		find_all_regions(bin, w, h, child);

		vector<vector<Point>> t_path;
		for (int i = 0; i < int(child.size()); i++)
		{
			point_to_bool(child[i], w, h, bin);
			dilate(bin, w, h);
			fill_region(bin, w, h);
			erose(bin, w, h);
			potrace(bin, w, h, t_path);
			for (int j = 0; j < int(t_path.size()); j++)
				paths.push_back(t_path[j]);
		}
	}
	inline void append_paths(const vector<vector<Point>> &to_append, vector<vector<Point>> &dst)
	{
		for (int i = 0; i < int(to_append.size()); i++)
			dst.push_back(to_append[i]);
	}
	inline bool generate_scanning_paths(const vector<bool> &c, int w, int h, int seed_x, int dx, float y, vector<vector<Point>> &paths)
	{
		paths.clear();
		bool added = false;
		int i = seed_x;
		int state = 0;
		int start_i = 0;
		vector<Point> path;
		while (i >= 0 && i < w)
		{
			bool b = c[int(y + 0.5f)*w + i];
			switch (state)
			{
			case 0:
				if (b)
				{
					state = 1;
					start_i = i;
				}
				break;
			case 1:
				if (!b)
				{
					state = 0;
					path.clear();
					path.push_back(Point(float(start_i - (0.5f*dx)), y)); //(标准值：0.5*dx)
					path.push_back(Point(float((i - dx) + (0.5f*dx)), y)); //(标准值：0.5f*dx)
					paths.push_back(path);
					added = true;
				}
				break;
			}
			i += dx;
		}
		if (state == 1)
		{
			path.clear();
			path.push_back(Point(float(start_i - (0.5f*dx)), y));  //(标准值：0.5*dx)
			path.push_back(Point(float((i - dx) + (0.5f*dx)), y)); //(标准值：0.5*dx)
			paths.push_back(path);
			added = true;
		}
		return added;
	}//end bool add_scanning_paths
	inline void generate_curve_path(const vector<bool> &data, int w, int h, float LINE_SPAN, vector<vector<vector<Point>>> &path)
	{
		vector<vector<Point>> t;
		//逐行提取
		bool ascending_order = true;
		for (float y = 0.0f; y < float(h - 1); y += LINE_SPAN)
		{
			bool b = false;
			if (ascending_order)
				b = generate_scanning_paths(data, w, h, 0, 1/*dx*/, y, t);
			else
				b = generate_scanning_paths(data, w, h, w - 1, -1/*dx*/, y, t);
			if (b)
			{
				path.push_back(t);
				ascending_order = !ascending_order;
			}
		}
	}
}

using namespace bin_image_implement;


void mdrawing::bin_image::remove_noises(BinImage &bin, const int &PIXEL_NUM)
{
	remain_regions(bin, PIXEL_NUM, INT_MAX);
}
int mdrawing::bin_image::remain_regions(BinImage &bin, const int &MN_NUM, const int &MX_NUM)
{
	int w = bin.get_w();
	int h = bin.get_h();
	auto &data = const_cast<vector<bool>&>(bin.get_data());

	vector<vector<UNIPoint>> region;
	find_all_regions(data, w, h, MN_NUM, MX_NUM, region);
	point_to_bool(region, w, h, data);
	return int(region.size());
}
bool mdrawing::bin_image::remain_largest_region(BinImage &bin, const int &QUALI)
{
	int w = bin.get_w();
	int h = bin.get_h();
	auto &data = const_cast<vector<bool>&>(bin.get_data());

	vector<UNIPoint> region;
	bool b = find_largest_regions(data, w, h, QUALI, region);
	point_to_bool(region, w, h, data);
	return b;
}

void mdrawing::bin_image::fill_regions(BinImage &bin)
{
	int w = bin.get_w();
	int h = bin.get_h();
	auto &data = const_cast<vector<bool>&>(bin.get_data());
	fill_region(data, w, h);
}

void mdrawing::bin_image::extract_red_regions(const BinImage &bin, const Image &image, BinImage &red)
{
	vector<bool> bin_red, bin_black;
	int w = bin.get_w();
	int h = bin.get_h();
	identify_red_black(bin.get_data(), image.get_data(), w, h, bin_black, bin_red);
	red.init(bin_red, w, h);
}

void mdrawing::bin_image::bool_operate_not(BinImage &bin)
{
	auto &data = const_cast<vector<bool>&>(bin.get_data());
	bool_operate_NOT(data);
}
void mdrawing::bin_image::bool_operate_and(const BinImage &src1, const BinImage &src2, BinImage &dst)
{
	auto &s1 = const_cast<vector<bool>&>(src1.get_data());
	auto &s2 = const_cast<vector<bool>&>(src2.get_data());
	auto &d  = const_cast<vector<bool>&>(dst.get_data());

	bool_operate_AND(s1, s2, d);
}
void mdrawing::bin_image::bool_operate_or(const BinImage &src1, const BinImage &src2, BinImage &dst)
{
	auto &s1 = const_cast<vector<bool>&>(src1.get_data());
	auto &s2 = const_cast<vector<bool>&>(src2.get_data());
	auto &d = const_cast<vector<bool>&>(dst.get_data());

	bool_operate_OR(s1, s2, d);
}
void mdrawing::bin_image::bool_operate_xor(const BinImage &src1, const BinImage &src2, BinImage &dst)
{
	auto &s1 = const_cast<vector<bool>&>(src1.get_data());
	auto &s2 = const_cast<vector<bool>&>(src2.get_data());
	auto &d = const_cast<vector<bool>&>(dst.get_data());

	bool_operate_XOR(s1, s2, d);
}
void mdrawing::bin_image::bool_operate_substract(const BinImage &src1, const BinImage &src2, BinImage &dst)
{
	auto &s1 = const_cast<vector<bool>&>(src1.get_data());
	auto &s2 = const_cast<vector<bool>&>(src2.get_data());
	auto &d = const_cast<vector<bool>&>(dst.get_data());

	bool_operate_SUB(s1, s2, d);
}

void mdrawing::bin_image::dilate(BinImage &bin, const int &R)
{
	int w = bin.get_w();
	int h = bin.get_h();
	auto &data = const_cast<vector<bool>&>(bin.get_data());

	bin_image_implement::dilate(data, w, h, R);
}

void mdrawing::bin_image::erose(BinImage &bin, const int &R)
{
	int w = bin.get_w();
	int h = bin.get_h();
	auto &data = const_cast<vector<bool>&>(bin.get_data());

	bin_image_implement::erose(data, w, h, R);
}

void mdrawing::bin_image::dilate(BinImage &bin)
{
	int w = bin.get_w();
	int h = bin.get_h();
	auto &data = const_cast<vector<bool>&>(bin.get_data());

	bin_image_implement::dilate(data, w, h);
}

void mdrawing::bin_image::erose(BinImage &bin)
{
	int w = bin.get_w();
	int h = bin.get_h();
	auto &data = const_cast<vector<bool>&>(bin.get_data());

	bin_image_implement::erose(data, w, h);
}

void mdrawing::bin_image::generate_outest_contour(const BinImage &src, Paths &dst)
{
	int w = src.get_w();
	int h = src.get_h();
	auto &bin = const_cast<vector<bool>&>(src.get_data());

	generate_cut_path(bin, w, h, dst);
}
void mdrawing::bin_image::generate_all_contour(const BinImage &src, Paths &dst)
{
	int w = src.get_w();
	int h = src.get_h();
	auto &bin = const_cast<vector<bool>&>(src.get_data());

	generate_cut_path_all_level(bin, w, h, dst);
}

void mdrawing::bin_image::generate_scanline_path(const BinImage &src, vector<Paths> &dst)
{
	int w = src.get_w();
	int h = src.get_h();
	auto &bin = const_cast<vector<bool>&>(src.get_data());

	generate_curve_path(bin, w, h, 1.0f, dst);
}